# 65/100 二分查找-在排序数组中查找元素的第一个和最后一个位置（好题）
# leetcode第34题: https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/?envType=study-plan-v2&envId=top-100-liked
# Date: 2025/1/15
from leetcode import test


def searchRange(nums: list[int], target: int) -> list[int]:
    n = len(nums)
    if n == 0:
        return [-1, -1]
    if n == 1:
        return [0, 0] if nums[0] == target else [-1, -1]

    l, r = 0, n - 1
    while l <= r:
        mid = ((r - l) >> 1) + l
        if nums[mid] == target:  # 使用二分法找到
            l, r = mid, mid
            lf, rf = False, False  # 判断是否执行了while循环
            while l >= 0 and nums[l] == target:
                l -= 1
                lf = True
            while r <= n - 1 and nums[r] == target:
                r += 1
                rf = True
            l += 1 if lf else 0
            r -= 1 if rf else 0
            return [l, r]
        elif nums[mid] < target:
            l = mid + 1
        else:
            r = mid - 1
    return [-1, -1]


def searchRange_opt(nums: list[int], target: int) -> list[int]:
    n = len(nums)
    # 特殊情况处理
    if n == 0:
        return [-1, -1]
    if n == 1:
        return [0, 0] if nums[0] == target else [-1, -1]

    def bisect(nums, n, target, lower):
        left, right, ans = 0, n - 1, len(nums)
        while left <= right:
            mid = (left + right) // 2
            # 重点在这里！只分为大于和小于等于target两种情况，lower情况下为大于等于target调整右指针，非lower时为小于等于target调整左指针
            if nums[mid] > target or (lower and nums[mid] >= target):
                right = mid - 1
                ans = mid
            else:  # 非lower的情况下
                left = mid + 1
        return ans

    left_idx = bisect(nums, n, target, True)
    right_idx = bisect(nums, n, target, False) - 1
    if left_idx <= right_idx < len(nums) and nums[left_idx] == target and nums[right_idx] == target:
        return [left_idx, right_idx]
    return [-1, -1]


if __name__ == '__main__':
    inp = [{"nums": [5, 7, 7, 8, 8, 10], "target": 8},
           {"nums": [5, 7, 7, 8, 8, 10], "target": 7},
           {"nums": [5, 7, 7, 8, 8, 10], "target": 6},
           {"nums": [1], "target": 1},
           {"nums": [2, 2], "target": 2},
           {"nums": [2, 2, 2, 2, 2, 2], "target": 2},
           {"nums": [], "target": 0},
           ]
    out = [[3, 4], [1, 2], [-1, -1], [0, 0], [0, 1], [0, 5], [-1, -1]]
    test.test_function(searchRange, inp, out)
    test.test_function(searchRange_opt, inp, out)
